package Algorithm.dynamicProgramming.knapsackDp;

import java.util.Arrays;

/**
 * 377. 组合总和 Ⅳ https://leetcode.cn/problems/combination-sum-iv/
 * 题目简述：给你一个由不同正整数组成的数组nums，和一个目标正整数target。从nums中找出并返回总和为target的元素排列的个数。
 */
public class CombinationSum4 {

    /**
     * 思路：完全背包-排列问题。使用爬楼梯的思路，爬到target的方案数等于爬到target减去nums中每一个数的方案数的总和
     * 1. 定义dp：dp[i]为凑成整数i的方案数
     * 2. 状态转移公式：凑成i的方案数等于所有dp[i-nums[j]]之和
     * 3. 初始化：dp[0] = 1;
     */
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        Arrays.sort(nums);
        dp[0] = 1;
        for (int i = 0;i <= target;i++) {
            for (int j = 0;j < nums.length && nums[j] <= i;j++) {
                dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
}
